/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package fpgrowth_demo;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.io.BufferedWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.HashSet;
import javax.swing.DefaultComboBoxModel;
import javax.swing.DefaultListModel;
import javax.swing.JComboBox;
import javax.swing.JLabel;
import javax.swing.JList;

/**
 *
 * @author TTIN
 */
public class FPTree {
    public FPTree()
    {
        //UpdateNode(Root,new Integer(2), new Double(1));
    }

    public Node Root = new Node();
    public ArrayList<HeaderNode> Header = new ArrayList<HeaderNode>();
    public Dimension draw_size = new Dimension();
    public int draw_mode = 0;
    public int num_of_transaction = 0;
    public double min_support=0.0001;
    public ArrayList<Integer> Condition = new ArrayList<Integer>();
    public int selected_cpb=-1;
    public int selected_header=-1;
    private DecimalFormat support_format = new DecimalFormat("#0.0000");

    public void setMinSupport(double minsupp)
    {
        min_support = minsupp;
    }

    public void BuildFromDatabase(Database data, int EndIndex)
    {

        Root = new Node();
        Header.clear();
        Condition.clear();
        for (int i=0;i<EndIndex;i++)
        {
            this.InsertTransaction(data.sorted_data.get(i));
        }
        num_of_transaction = EndIndex;

        SortHeaderNode();
        draw_size.width = 0;
        draw_size.height = 0;
        UpdateNode(Root, new Integer(3), new Double(MainFrame.NODEWIDTH));
        if (draw_size.height < (Header.size()+3)*MainFrame.NODEPADDINGY+100)
            draw_size.height = (Header.size()+3)*MainFrame.NODEPADDINGY+100;
        markCPBNodeBaseOnCondition();
        

    }

    public void SortHeaderNode()
    {
        for (int i=0;i<Header.size();i++)
            for (int j=i+1;j<Header.size();j++)
            {
                if ((Header.get(j).count>Header.get(i).count) ||
                        ((Header.get(j).count==Header.get(i).count)&&(Header.get(j).item<Header.get(i).item)))
                {
                    HeaderNode t1 = Header.remove(j);
                    HeaderNode t2 = Header.remove(i);
                    Header.add(i,t1);
                    Header.add(j,t2);
                }
            }

    }

    public void InsertTransaction(ArrayList<Integer> t)
    {
        Node cur = this.Root;
        for (Integer i:t)
        {
            cur = this.InsertItem(cur,i);
        }
    }

    public Node InsertItem(Node n, Integer i)
    {
        for (Node node:n.child)
            if (node.item==i)
            {
                node.count++;
                for (HeaderNode h:Header)
                    if (h.item == node.item)
                        h.count++;
                return node;
            }
        Node node = new Node();
        node.item = i;
        node.count = 1;
        node.parent =n;
        n.child.add(node);

        boolean existHeader = false;
        for (HeaderNode h:Header)
        {
            if (h.item == node.item)
            {
                h.link.add(node);
                h.count+=node.count;
                existHeader = true;
                break;
            }
        }
        if (!existHeader)
        {
            HeaderNode h = new HeaderNode();
            h.item = i;
            h.count = 1;
            h.link.add(node);
            Header.add(h);
        }

        
        return node;
    }

    public Double UpdateNode(Node n, Integer row, Double endx)
    {
        if (n.child.size()>0)
        {
            Integer nextrow = new Integer(row+1);
            for (Node node:n.child)
                endx = UpdateNode(node, nextrow, endx);
            n.x = (int)(n.child.get(0).x + n.child.get(n.child.size()-1).x)/2;
            n.y = (int) row * MainFrame.NODEPADDINGY;

            return endx;
        }
        else
        {
            endx = endx.doubleValue() + MainFrame.NODEPADDINGX;
            n.x = endx.intValue();
            n.y = (int) row * MainFrame.NODEPADDINGY;

            if (n.x+MainFrame.NODEWIDTH+100>draw_size.width)
                draw_size.width = n.x+MainFrame.NODEWIDTH+100;
            if (n.y+MainFrame.NODEHEIGHT+100>draw_size.height)
                draw_size.height = n.y+MainFrame.NODEHEIGHT+100;


            return endx;
        }
        /*if (endx<x-MainFrame.NODEPADDINGX)
            endx = x - MainFrame.NODEPADDINGX;
        n.x = (int) ((startx + endx) / 2);
        n.y = (int) row * MainFrame.NODEPADDINGY;*/
    }

    public void drawTree(Graphics g)
    {
        for (HeaderNode hnode:Header)
        {
            g.setColor(new Color(50,50,150,255));
            g.fillRect(MainFrame.NODEPADDINGX/2, (Header.indexOf(hnode)+4)* MainFrame.NODEPADDINGY, MainFrame.NODEWIDTH, MainFrame.NODEHEIGHT);
            g.drawString(String.valueOf(hnode.item)+/*":"+String.valueOf(hnode.count)+*/":"+String.valueOf(hnode.count_cpb),MainFrame.NODEPADDINGX/2, (Header.indexOf(hnode)+4)* MainFrame.NODEPADDINGY);
            //g.drawRect(x, y, x+MainFrame.NODEWIDTH, y+ MainFrame.NODEHEIGHT);
        }

        if (selected_header>=0)
        {
            HeaderNode hnode= Header.get(selected_header);
            for (Node node:hnode.link)
            {
                g.setColor(new Color(50,50,150,200));
                g.drawRect(node.x-2, node.y-2, MainFrame.NODEWIDTH+4, MainFrame.NODEHEIGHT+4);
                g.drawRect(node.x-3, node.y-3, MainFrame.NODEWIDTH+6, MainFrame.NODEHEIGHT+6);
            }
        }


        g.setColor(Color.BLACK);
        if (isSinglePath_CPB())
            g.drawString("Single Path", 10, 15);
        else
            g.drawString("Not Single Path", 10, 15);
        g.drawString("Number of transactions: "+String.valueOf(num_of_transaction), 10, 35);
        g.drawString("Min support: "+String.valueOf(min_support), 10, 55);
        drawNode(Root,g);
    }

    public void drawNode(Node node,Graphics g)
    {
        if (node.flag_cpb_selected==1)
        {
            g.setColor(new Color(255,0,0,255));
            g.drawRect(node.x-2, node.y-2, MainFrame.NODEWIDTH+4, MainFrame.NODEHEIGHT+4);
        }

        if (node==Root)
        {
            g.setColor(new Color(0,125,0,255));
            g.fillRect(node.x, node.y, MainFrame.NODEWIDTH, MainFrame.NODEHEIGHT);
            g.drawString("Root", node.x, node.y-4);
        }
        else
        {
            if ((node.flag_cfptree==1)||(Condition.isEmpty()))
            {
                g.setColor(new Color(0,125,0,255));
                g.fillRect(node.x, node.y, MainFrame.NODEWIDTH, MainFrame.NODEHEIGHT);
                g.setColor(Color.BLACK);
                g.drawString(String.valueOf(node.item)+/*":"+String.valueOf(node.count)+*/":"+String.valueOf(node.count_cpb)/*+":"+String.valueOf(node.flag_cpb)*/, node.x, node.y-4);
            }
            else if (node.flag_cpb==Condition.size())
            {
                g.setColor(new Color(0,125,0,50));
                g.fillRect(node.x, node.y, MainFrame.NODEWIDTH, MainFrame.NODEHEIGHT);
                g.drawString(String.valueOf(node.item)+/*":"+String.valueOf(node.count)+*/":"+String.valueOf(node.count_cpb)/*+":"+String.valueOf(node.flag_cpb)*/, node.x, node.y-4);
            }
            else if(node.flag_cpb < 0)
            {
                g.setColor(new Color(255,125,125,50));
                g.fillRect(node.x, node.y, MainFrame.NODEWIDTH, MainFrame.NODEHEIGHT);
                g.setColor(Color.BLACK);
                g.drawString(String.valueOf(node.item)+/*":"+String.valueOf(node.count)+*/":"+String.valueOf(node.count_cpb)/*+":"+String.valueOf(node.flag_cpb)*/, node.x, node.y-4);
            }
            else
            {
                g.setColor(new Color(0,0,0,50));
                g.drawRect(node.x, node.y, MainFrame.NODEWIDTH, MainFrame.NODEHEIGHT);
                g.drawString(String.valueOf(node.item)+/*":"+String.valueOf(node.count)+*/":"+String.valueOf(node.count_cpb)/*+":"+String.valueOf(node.flag_cpb)*/, node.x, node.y-4);
            }


        }

        for (Node subnode:node.child)
        {
            if (subnode.flag_cpb==Condition.size())
                g.setColor(new Color(0,125,0,125));
            else
                g.setColor(new Color(0,0,0,125));
            g.drawLine(subnode.x+(int)MainFrame.NODEWIDTH/2, subnode.y, node.x+(int)MainFrame.NODEWIDTH/2, node.y+ MainFrame.NODEHEIGHT);
            drawNode(subnode,g);
        }
    }



    public HeaderNode getHeaderNode(int item)
    {
        for (HeaderNode node:Header)
        {
            if (node.item == item)
                return node;
        }
        return null;
    }


    public void clearFlag(Node node)
    {
        node.flag_cpb = 0;
        node.flag_cfptree = 0;
        for(Node childnode:node.child)
            clearFlag(childnode);
    }

    public void clearCountCPB(Node n)
    {
        n.count_cpb=0;
        for (Node subn:n.child)
            clearCountCPB(subn);
    }

    public void markCPBNode(Node node, int count_cpb, int flag_match)
    {
        if (node==null) return;
        if (node.flag_cpb!=flag_match) return;
        node.flag_cpb++;
        //node.count_cpb += count_cpb;
        getHeaderNode(node.item).count_cpb += count_cpb;
        if (node!=Root)
            markCPBNode(node.parent, count_cpb, flag_match);
    }

    public void clearHeaderCPB()
    {
        for (HeaderNode hnode:Header)
            hnode.count_cpb = 0;
    }

    public int distanceFromRoot(Node node)
    {
        if (node==Root) return 0;
        else
            if (node.flag_cfptree==1)
                return distanceFromRoot(node.parent)+1;
            else return distanceFromRoot(node.parent);
    }

    private boolean isSingleSubPath_CPB(Node node)
    {
        int count=0;
        for (Node subnode:node.child)
        {
            if (!isSingleSubPath_CPB(subnode)) return false;
            if (subnode.flag_cfptree==1)//(subnode.flag_cpb==Condition.size())
                count ++;
        }
        if (count>1) return false;
        return true;
    }

    private boolean isSinglePath_CPB()
    {
        if (Header.isEmpty()) return true;
        HashSet<Integer> Header_level = new HashSet<Integer>();
        for (HeaderNode hnode:Header)
        {
            double supp =(double)hnode.count_cpb/num_of_transaction;
            if (supp>=min_support)
            {
                int distance = 0;
                for (Node node:hnode.link)
                    if (node.flag_cfptree==1)
                    {
                        if (distance==0)
                        {
                            distance = distanceFromRoot(node);
                            if (Header_level.contains(distance)) return false;
                            else Header_level.add(distance);
                        }
                        else if (distance!=distanceFromRoot(node)) return false;
                    }
            }
        }
        return true;

        //return isSingleSubPath_CPB(Root);

        /*for (HeaderNode hnode:Header)
            if (hnode.count_cpb>0)
            {
                for (Node node:hnode.link)
                {
                    if ((node.flag==Condition.size()) && (distanceFromRoot(node)!=distanceFromRoot(hnode.link.get(0)))) return false;
                }
            }
        return true;*/
        /*Integer condition = Condition.get(Condition.size()-1);

        Node checknode = null;
        for (Node node:getHeaderNode(condition).link)
        {
            Node aflast = node;
            while (aflast.parent!=Root)
                aflast = aflast.parent;
            if (checknode==null)
                checknode = aflast;
            else if (aflast!=checknode)
                return false;
        }
        return true;*/
    }

    private boolean countCPB(Node node, int cpb, int check)
    {
        if (Condition.contains(node.item))
        {
            if (cpb==0)
                cpb = node.count;
            else
                cpb = Math.min(cpb, node.count);
            check++;
        }

        if (node.flag_cpb == Condition.size() && check == Condition.size())
            node.count_cpb+= cpb;
        if (node!=Root)
            return countCPB(node.parent, cpb, check);
        else return (check==Condition.size());
    }

    private boolean markCondtition(Node node, int count_condition)
    {
        if (node==null) return false;
        else
        {
            //if (node.flag_cfptree==1) return true;
            if (node.flag_cpb==Condition.size() && count_condition==Condition.size()) return true;
            else
            {
                if (Condition.contains(node.item))
                {
                    if (markCondtition(node.parent,count_condition+1))
                    {
                        node.flag_cpb = -1;
                        return true;
                    }
                    else return false;
                }
                else
                    return markCondtition(node.parent,count_condition);
            }
        }
    }

    public void markCPB(Node node)
    {
        node.count_cpb = node.count;
        for (Node subnode:node.child)
            markCPB(subnode);
    }

    public void markCPBNodeBaseOnCondition()
    {
        //if
        clearFlag(Root);
        clearCountCPB(Root);
        for (Integer condition:Condition)
        {
            //clearCountCPB(Root);
            HeaderNode hnode = getHeaderNode(condition);
            for (Node node:hnode.link)
                if (node.flag_cpb==Condition.indexOf(condition))
                {

                    markCPBNode(node.parent, node.count, node.flag_cpb);
                    //if (node.count_cpb==0) node.count_cpb=node.count;
                    //node.parent.count_cpb += node.count_cpb;
                }
        }

        if (!Condition.isEmpty())
            for (Node node:getHeaderNode(Condition.get(0)).link)
                countCPB(node,0,0);

        else
            markCPB(Root);


                //markCondtition(node);

        clearHeaderCPB();
        for (HeaderNode hnode:Header)
        {
            for (Node node:hnode.link)
            {
                if (node.flag_cpb==Condition.size())
                    hnode.count_cpb+=node.count_cpb;
            }
            double supp = (double)hnode.count_cpb/num_of_transaction;
            if ((Condition.isEmpty())||(supp>=min_support))
            {
                for (Node node:hnode.link)
                    if (node.flag_cpb==Condition.size())
                        node.flag_cfptree = 1;
            }
        }

        if (!Condition.isEmpty())
        for (Node node:getHeaderNode(Condition.get(0)).link)
            markCondtition(node,0);

    }

    public boolean nextCombination(int length, boolean[] combination)
    {
        if (length==0) return false;
        int index=length-1;
        while ((index>=0)&&(combination[index]==true)) index--;
        if (index==-1) return false;
        else
        {
            combination[index]=true;
            while (index+1<length)
            {
                index++;
                combination[index]=false;
            }
            return true;
        }
    }



    public void updateColor(Node node)
    {
        if (node==Root)
            node.color = Color.DARK_GRAY;
        else
        {
            if (node.flag_cpb==Condition.size())
                node.color = Color.RED;
            else
                if (Condition.contains(Integer.valueOf(node.item)))
                    node.color = Color.GREEN;
                else
                    node.color = Color.BLACK;
        }

        for (Node subnode:node.child)
            updateColor(subnode);
    }


     
    /*public void generateCombination(Node n,DefaultListModel model)
    {
        if (model.size()>10000) return;
        NumberFormat myFormat = new DecimalFormat("#0.0000");
        if (n.child.isEmpty())
        {
            if (n==Root) return ;
            model.addElement(String.valueOf(n.item)+ " Support:" + myFormat.format((double)(n.count)/num_of_transaction));
        }
        else
        {
            
            int startindex = model.getSize();
            generateCombination(n.child.get(0), model);
            if (n==Root) return ;
            int endindex = model.getSize();
            for (int i=startindex;i<endindex;i++)
            {
                String s = model.getElementAt(i).toString();
                String substring = s.substring(s.indexOf(":")+1,s.length()-1);
                s = s.substring(0,s.lastIndexOf(" Support"));
                Double supp = Double.parseDouble(substring);
                if (((double)(n.count)/num_of_transaction)<supp)
                    supp = ((double)(n.count)/num_of_transaction);
                model.addElement(String.valueOf(n.item) + " " + s + " Support:" + myFormat.format(supp));
                if (model.size()>10000) return;
            }
            model.addElement(String.valueOf(n.item) + " Support:" + myFormat.format((double)(n.count)/num_of_transaction));
        }
    }

    public void FrequentPattern(DefaultListModel model)
    {
        if (model.size()>10000) return;
        if (isSinglePath(Root))
        {
            System.out.println(Root.child.size()+ " " + Header.size());

            generateCombination(Root,model);
            return ;//generateCombination(Root);
        }
        else
        {

            //HashSet<HashSet<Integer>> arr = new HashSet<HashSet<Integer>>();
            if (Root.child.isEmpty())
                return ;//arr;
            for (int i = Header.size()-1;i>=0;i--)
            {
                FPTree subtree = this.clone();
                subtree.markCPBNodeBaseOnCondition(Header.get(i).item);
                subtree.pruneTree();
                subtree.FrequentPattern(model);
                if (model.size()>10000) return;

            }
            //return arr;
        }
    }*/


    public void writeHeaderTableToComboBox(JComboBox combo_box)
    {
        DefaultComboBoxModel model = new DefaultComboBoxModel();
        for (HeaderNode hnode:Header)
        {
            double supp = (double)hnode.count_cpb/num_of_transaction;
            if ((Condition.isEmpty()) || (supp>=min_support))
                model.addElement(hnode.item);
        }
        combo_box.setModel(model);
        combo_box.setSelectedIndex(-1);
    }

    public void writeConditionToLabel(JLabel label)
    {
        String s="";
        for (Integer condition:Condition)
            s= condition.toString() + " " +s;
        s = "Condition Patterns: " +s;
        label.setText(s);
    }
    
    private void pushCPBFromNodeToArray(Node node, ArrayList<Integer> array)
    {
        if (node.flag_cpb>0)
            array.add(0, node.item);
        if (node.parent!=Root)
            pushCPBFromNodeToArray(node.parent, array);
    }

    public void writeCPBtoList(JList list)
    {
        DefaultListModel model = new DefaultListModel();
        if (!Condition.isEmpty())
        {
            model.addElement(" ");
            HeaderNode hnode = getHeaderNode(Condition.get(0));
            for (Node node:hnode.link)
            {
                if (node.flag_cpb<0)
                {
                    ArrayList<Integer> array = new ArrayList<Integer>();
                    pushCPBFromNodeToArray(node, array);
                    String s="{ ";
                    for (Integer i:array)
                        s+= i+" ";
                    s+="| ";
                    for (Integer i:Condition)
                        s+= i+" ";
                    s+="} : "+node.count;
                    model.addElement(s);
                }
            }

        }
        list.setModel(model);
    }


    private void clearFlagCPBSelected(Node node)
    {
        node.flag_cpb_selected = 0;
        for (Node subnode:node.child)
            clearFlagCPBSelected(subnode);
    }

    public void updateSelectedCPBColor()
    {
        clearFlagCPBSelected(Root);
        if (Condition.isEmpty()) return;
        if (selected_cpb<0) return;
        HeaderNode hnode = getHeaderNode(Condition.get(Condition.size()-1));
        Node node = hnode.link.get(selected_cpb).parent;
        while (node!=Root)
        {
            node.flag_cpb_selected = 1;
            node = node.parent;
        }
    }

    public void updateConditionAndWriteFrequentSetToList(JList list)
    {
        markCPBNodeBaseOnCondition();        
        DefaultListModel model = new DefaultListModel();
        FPGrowth(model,0);
        list.setModel(model);
        markCPBNodeBaseOnCondition();
        selected_cpb=-1;
    }

    public void FPGrowth(Object obj, int mode)
    {
        try
        {
            DefaultListModel model=null;
            BufferedWriter writebuffer=null;
            if (mode==0)
                model = (DefaultListModel)obj;
            else
                writebuffer = (BufferedWriter)obj;

            if (Header.isEmpty()) return;
            if (isSinglePath_CPB())
            {
                int header_count=0;
                for (HeaderNode hnode:Header)
                    if (calculateCPBSupport(hnode)>=min_support)
                        header_count++;
                boolean[] combination = new boolean[header_count];
                for (int i=0;i<header_count;i++)
                    combination[i]=false;

                if (!Condition.isEmpty())
                {
                    String s="{ ";
                    for (int i=Condition.size()-1;i>=0;i--)
                        s+= Condition.get(i) + " ";

                    HeaderNode hnode = getHeaderNode(Condition.get(0));
                    int count=0;
                    for (Node node:hnode.link)
                        if (node.flag_cpb<0)
                            count+=node.count;


                    s+="} : "+ support_format.format(calculateSupport(count));
                    if (model!=null)
                    {
                        model.addElement(s);
                        if (model.size()>5000) return;
                    }
                    else
                    {
                        writebuffer.write(s);
                        writebuffer.newLine();
                    }
                }
                while (nextCombination(header_count, combination))
                {
                    int index=0;
                    String s="{ ";
                    int min_count = num_of_transaction;
                    for (HeaderNode hnode:Header)
                        if (calculateCPBSupport(hnode)>=min_support)
                        {
                            if (combination[index]) s+=hnode.item+ " ";
                            if (min_count>hnode.count_cpb) min_count = hnode.count_cpb;
                            index++;
                        }
                    for (int i=Condition.size()-1;i>=0;i--)
                        s+= Condition.get(i) + " ";

                    s+= "} : "+support_format.format(calculateSupport(min_count));
                    if (model!=null)
                    {
                        model.addElement(s);
                        if (model.size()>5000) return;
                    }
                    else
                    {
                        writebuffer.write(s);
                        writebuffer.newLine();
                    }
                }

            }
            else
            {
                int last_condition_index;
                if (Condition.isEmpty())
                    last_condition_index = Header.size()-1;
                else
                    last_condition_index = Header.indexOf(getHeaderNode(Condition.get(Condition.size()-1)));
                if (last_condition_index>0)
                {
                    for (int i=last_condition_index-1;i>=0;i--)
                    {
                        HeaderNode hnode = Header.get(i);
                        if (calculateCPBSupport(hnode)>=min_support)
                        {
                            Condition.add(hnode.item);
                            markCPBNodeBaseOnCondition();
                            FPGrowth(obj,mode);
                            Condition.remove(Condition.size()-1);
                            markCPBNodeBaseOnCondition();
                            if ((model!=null) && (model.size()>5000)) return;
                        }
                    }
                }
            }
        }
        catch (Exception e)
        {
            System.out.println(e.getMessage());
        }
    }
    

    public void writeHeaderToList(JList list)
    {
        DefaultListModel model = new DefaultListModel();
        model.addElement(" ");
        
        //if (!Condition.isEmpty())
        for (HeaderNode hnode:Header)
        {
            DecimalFormat myFormat= new DecimalFormat("#0.0000");
            double oldsupp = (double)hnode.count/num_of_transaction;
            double newsupp = (double)hnode.count_cpb/num_of_transaction;
            model.addElement(hnode.item + ":"+myFormat.format(oldsupp)+":"+myFormat.format(newsupp));
        }
        list.setModel(model);
    }

    public double calculateCPBSupport(Node node)
    {
        return (double)node.count_cpb/num_of_transaction;
    }

    public double calculateCPBSupport(HeaderNode hnode)
    {
        return (double)hnode.count_cpb/num_of_transaction;
    }

    public double calculateSupport(Node node)
    {
        return (double)node.count/num_of_transaction;
    }

    public double calculateSupport(HeaderNode hnode)
    {
        return (double)hnode.count/num_of_transaction;
    }

    public double calculateSupport(int count)
    {
        return (double)count/num_of_transaction;
    }

}
